#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 树节点类
struct TreeNode {
    int number; // 编号
    int value; // 节点值
    vector<TreeNode*> children; // 子节点

    TreeNode(int num, int val) : number(num), value(val) {}
};

// 在树中寻找深度最小的目标节点，并返回其编号
int findNode(TreeNode* root, int t) {
    // 使用一个队列保存待搜索的节点
    queue<TreeNode*> queue;
    queue.push(root);

    // BFS搜索
    while (!queue.empty()) {
        // 从队列中取出当前树节点，进行下一步搜索
        TreeNode* parentNode = queue.front();
        queue.pop();

        // 进一步搜索它的所有子节点
        for (TreeNode* child : parentNode->children) {
            // BFS找到第一个答案便可以直接返回
            if (child->value == t)
                return child->number;
            // 将新找到的节点放入队列
            queue.push(child);
        }
    }

    // 若搜索完毕还未找到答案，说明无解
    return -1;
}

// 构建树，返回根节点
TreeNode* buildTree(const vector<int>& parents, const vector<int>& values) {
    int n = parents.size();
    vector<TreeNode*> tree(n);
    for (int i = 0; i < n; i++) {
        tree[i] = new TreeNode(i + 1, values[i]);
        int parentNum = parents[i];
        if (parentNum > 0) {
            TreeNode* parent = tree[parentNum - 1];
            parent->children.push_back(tree[i]);
        }
    }
    return tree[0];
}

int main() {
    vector<int> parents = {-1, 1, 1, 1, 1, 3, 3, 4, 5, 5, 7, 8, 9, 11};
    vector<int> values = {9, 7, 4, 1, 6, 8, 2, 9, 8, 7, 6, 8, 2, 5};
    TreeNode* root = buildTree(parents, values);
    int treeNum = findNode(root, 8);
    cout << "树节点查找答案为: " << treeNum << endl;
    return 0;
}